#include <iostream>
#include <windows.h>

typedef int KeyType;
typedef int InfoType;

typedef struct {
    KeyType key;
    InfoType otherInfo;
} RecdType;

typedef struct {
    RecdType r[101];
    int length;
} SqList;

void setup() {
    SetConsoleOutputCP(CP_UTF8);
    SetConsoleCP(CP_UTF8);
    setvbuf(stdout, NULL, _IONBF, 0);
}

// 插入排序
void Sort_Insert(SqList &L) {
    int compareCount = 0;
    int moveCount = 0;
    for (int i = 2; i <= L.length; ++i) {
        if (++compareCount && L.r[i].key < L.r[i - 1].key) {
            L.r[0] = L.r[i];
            moveCount++;
            int j;
            for (j = i - 1; j >= 1 && ++compareCount && L.r[0].key < L.r[j].key; --j) {
                L.r[j + 1] = L.r[j];
                moveCount++;
            }
            L.r[j + 1] = L.r[0];
            moveCount++;
        }
    }
    std::cout << "比较次数: " << compareCount << ", 移动次数: " << moveCount << std::endl;
}

// 希尔排序
void Sort_Shell(SqList &L, int dk) {
    int compareCount = 0;
    int moveCount = 0;
    for (int i = 1 + dk; i <= L.length; ++i) {
        if (++compareCount && L.r[i].key < L.r[i - dk].key) {
            L.r[0] = L.r[i];
            moveCount++;
            L.r[i] = L.r[i - dk];
            moveCount++;
            int j;
            for (j = i - dk; j > 0 && ++compareCount && L.r[0].key < L.r[j].key; j -= dk) {
                L.r[j + dk] = L.r[j];
                moveCount++;
            }
            L.r[j + dk] = L.r[0];
            moveCount++;
        }
    }
    std::cout << "比较次数: " << compareCount << ", 移动次数: " << moveCount << std::endl;
}

// 冒泡排序
void Sort_Bubble(SqList &L) {
    int compareCount = 0;
    int moveCount = 0;
    for (int i = L.length; i > 1; --i) {
        bool swapped = false;
        for (int j = 1; j < i; ++j) {
            if (++compareCount && L.r[j].key > L.r[j + 1].key) {
                std::swap(L.r[j], L.r[j + 1]);
                moveCount += 3; // 三次赋值
                swapped = true;
            }
        }
        if (!swapped) break;
    }
    std::cout << "比较次数: " << compareCount << ", 移动次数: " << moveCount << std::endl;
}

// 快速排序辅助函数
int Partition(SqList &L, int low, int high, int &compareCount, int &moveCount) {
    L.r[0] = L.r[low];
    moveCount++;
    KeyType pivotkey = L.r[low].key;
    while (low < high) {
        while (low < high && ++compareCount && L.r[high].key >= pivotkey) high--;
        if (low < high) {
            L.r[low++] = L.r[high];
            moveCount++;
        }
        while (low < high && ++compareCount && L.r[low].key <= pivotkey) low++;
        if (low < high) {
            L.r[high--] = L.r[low];
            moveCount++;
        }
    }
    L.r[low] = L.r[0];
    moveCount++;
    return low;
}

void QuickSort(SqList &L, int low, int high, int &compareCount, int &moveCount) {
    if (low < high) {
        int pivotloc = Partition(L, low, high, compareCount, moveCount);
        QuickSort(L, low, pivotloc - 1, compareCount, moveCount);
        QuickSort(L, pivotloc + 1, high, compareCount, moveCount);
    }
}

void Sort_Quick(SqList &L) {
    int compareCount = 0;
    int moveCount = 0;
    QuickSort(L, 1, L.length, compareCount, moveCount);
    std::cout << "比较次数: " << compareCount << ", 移动次数: " << moveCount << std::endl;
}

// 选择排序
void Sort_Select(SqList &L) {
    int compareCount = 0;
    int moveCount = 0;
    for (int i = 1; i < L.length; ++i) {
        int min = i;
        for (int j = i + 1; j <= L.length; ++j) {
            if (++compareCount && L.r[j].key < L.r[min].key) {
                min = j;
            }
        }
        if (min != i) {
            std::swap(L.r[i], L.r[min]);
            moveCount += 3;
        }
    }
    std::cout << "比较次数: " << compareCount << ", 移动次数: " << moveCount << std::endl;
}

// 归并排序辅助函数
void Merge(RecdType SR[], RecdType TR[], int i, int m, int n, int &compareCount, int &moveCount) {
    int j = m + 1, k = i;
    while (i <= m && j <= n) {
        if (++compareCount && SR[i].key <= SR[j].key) {
            TR[k++] = SR[i++];
            moveCount++;
        } else {
            TR[k++] = SR[j++];
            moveCount++;
        }
    }
    while (i <= m) {
        TR[k++] = SR[i++];
        moveCount++;
    }
    while (j <= n) {
        TR[k++] = SR[j++];
        moveCount++;
    }
}

void M_Sort(RecdType SR[], RecdType TR1[], int s, int t, int &compareCount, int &moveCount) {
    RecdType TR2[101];
    if (s == t) {
        TR1[s] = SR[s];
        moveCount++;
    } else {
        int m = (s + t) / 2;
        M_Sort(SR, TR2, s, m, compareCount, moveCount);
        M_Sort(SR, TR2, m + 1, t, compareCount, moveCount);
        Merge(TR2, TR1, s, m, t, compareCount, moveCount);
    }
}

void Sort_Merge(SqList &L) {
    int compareCount = 0;
    int moveCount = 0;
    M_Sort(L.r, L.r, 1, L.length, compareCount, moveCount);
    std::cout << "比较次数: " << compareCount << ", 移动次数: " << moveCount << std::endl;
}

int main() {
    setup();

    SqList L;
    int choice;

    std::cout << "请输入要排序的元素个数(1-100): ";
    std::cin >> L.length;
    if (L.length < 1 || L.length > 100) {
        std::cout << "输入范围错误，请输入1-100之间的整数。" << std::endl;
        return 1;
    }

    std::cout << "请依次输入" << L.length << "个整数:\n";
    for (int i = 1; i <= L.length; ++i) {
        std::cout << "元素" << i << ": ";
        std::cin >> L.r[i].key;
        L.r[i].otherInfo = 0;
    }

    std::cout << "\n原始数组: ";
    for (int i = 1; i <= L.length; ++i) {
        std::cout << L.r[i].key << " ";
    }
    std::cout << std::endl;

    while (true) {
        SqList temp = L;

        std::cout << "\n请选择排序算法:\n";
        std::cout << "1. 插入排序\n";
        std::cout << "2. 希尔排序\n";
        std::cout << "3. 冒泡排序\n";
        std::cout << "4. 快速排序\n";
        std::cout << "5. 选择排序\n";
        std::cout << "6. 归并排序\n";
        std::cout << "0. 退出\n";
        std::cout << "请输入选择: ";
        std::cin >> choice;

        if (choice == 0) break;

        switch (choice) {
            case 1:
                Sort_Insert(temp);
                std::cout << "插入排序结果: ";
                break;
            case 2:
                Sort_Shell(temp, temp.length / 2);
                std::cout << "希尔排序结果: ";
                break;
            case 3:
                Sort_Bubble(temp);
                std::cout << "冒泡排序结果: ";
                break;
            case 4:
                Sort_Quick(temp);
                std::cout << "快速排序结果: ";
                break;
            case 5:
                Sort_Select(temp);
                std::cout << "选择排序结果: ";
                break;
            case 6:
                Sort_Merge(temp);
                std::cout << "归并排序结果: ";
                break;
            default:
                std::cout << "无效选择，请重新输入。\n";
                continue;
        }

        // 输出排序结果
        for (int i = 1; i <= temp.length; ++i) {
            std::cout << temp.r[i].key << " ";
        }
        std::cout << std::endl;

        // 验证排序是否正确
        bool sorted = true;
        for (int i = 1; i < temp.length; ++i) {
            if (temp.r[i].key > temp.r[i + 1].key) {
                sorted = false;
                break;
            }
        }
        if (sorted) {
            std::cout << "验证: 排序正确!\n";
        } else {
            std::cout << "验证: 排序错误!\n";
        }
    }

    return 0;
}